package codingforgreat.lchot150;

import java.util.HashMap;

public class Lc149 {
    public int maxPoints(int[][] points) {
        if(points == null){
            return 0;
        }
        if(points.length <= 2){
            return points.length;
        }
        HashMap<Integer,HashMap<Integer,Integer>> map = new HashMap<>();
        int result = 0;
        for(int i = 0;i < points.length;i++){
            map.clear();
            int sameX = 0;
            int sameY = 0;
            int line = 0;
            int samePosition = 1;
            for(int j = i + 1;j < points.length;j++){
                int x = points[j][0] - points[i][0];
                int y = points[j][1] - points[i][1];
                if(x == 0 && y == 0){
                    samePosition++;
                }else if(x == 0){
                    sameX++;
                }else if(y == 0){
                    sameY++;
                }else{
                    int gcb = gcb(x,y);
                    x /= gcb;
                    y /= gcb;
                    if(!map.containsKey(x)){
                        map.put(x,new HashMap<Integer,Integer>());
                    }
                    if(!map.get(x).containsKey(y)){
                        map.get(x).put(y,0);
                    }
                    map.get(x).put(y,map.get(x).get(y) + 1);
                    line = Math.max(line,map.get(x).get(y));
                }
            }
            result = Math.max(result,Math.max(sameX,Math.max(sameY,line)) + samePosition);
        }
        return result;

    }
    public int gcb(int x,int y){
        return y == 0 ? x : gcb(y,x%y);
    }
}
